/**
 * @file     hasPathSum.ts
 * @brief    [112. 路径总和](https://leetcode.cn/problems/path-sum/)
 * @author   Zhu
 * @date     2022-11-16 23:39:58
 */

import { TreeNode } from '../helper';

/**
 * 保存节点同时保存当时的节点路径和
 */
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (!root) return false;

    const stack: [TreeNode, number][] = [[root, root.val]];
    while (stack.length > 0) {
        const [cur, sum] = stack.pop()!;

        if (!cur.left && !cur.right) {
            if (sum === targetSum) return true;
        }

        if (cur.right) {
            stack.push([cur.right, sum + cur.right.val]);
        }
        if (cur.left) {
            stack.push([cur.left, sum + cur.left.val]);
        }
    }

    return false;
}
